<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        插值查找法的公式为：
                        mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)<br>
                        其中，key是要查找的键值，data[high]、data[low]是剩余待查找记录中的最大值和最小值。
                        假设数据项数为n，其插值查找法的步骤如下：
                    </div>
                    <div>
                        （1）将记录从小到大的顺序给予1、2、3、...、n的编号。
                    </div>
                    <div>
                        （2）令low=1，high=n。
                    </div>
                    <div>
                        （3）当low&lt;high时，重复执行步骤4和步骤5。
                    </div>
                    <div>
                        （4）令mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)
                    </div>
                    <div>
                        （5）若key&lt;keymid且high！=mid=-1，则令high=mid=-1
                    </div>
                    <div>
                        （6）若key=keymid,则表示成功查找到键值的位置
                    </div>
                    <div>
                        （7）若key>keymid且low！=mid+1，则令low=mid+1
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                            #include &lt;stdio.h>
                            #include &lt;stdlib.h>
                            
                            void manual_array();                             /*手动输入数组*/     
                            void Interpolation_search(int *arr, int key, int sz);   /*二分法查找(升序降序都可)*/           
                            int size;
                            int a[512];
                            
                            int main(int argc, char *argv[])
                            {
                                int key;
                                manual_array();
                            
                                printf("Please enter the number you want to find:");
                                scanf("%d", &key);
                            
                                Interpolation_search(a, key, size);
                                return 0;
                            }
                            
                            
                            /*手动输入数组*/
                            void manual_array()
                            {
                                printf("Please enter the build array size:");
                                scanf("%d\n", &size);
                                for (int i = 0; i &lt; size; i++)
                                {
                                    scanf("%d", &a[i]);
                                    for (int j = 0; j &lt; i; j++)
                                    {
                                        while (a[i] == a[j])
                                        {
                                            printf("ERROR: Duplicate input data.Please try again\n");
                                            j = 0;
                                            scanf("%d\n", &a[i]);
                                        }
                                    }
                                }
                            
                                printf("Array[%d]:", size);
                                for (int i = 0; i &lt; size; i++)
                                {
                                    printf("%d ", a[i]);
                                }
                                printf("\n");
                            }
                            
                            /*[2]二分法查找(升序降序都可)*/
                            void Interpolation_search(int *arr, int key, int sz)
                            {
                                printf("\n");
                                int left = 0;       //左边
                                int right = sz - 1; //右边
                                int mid;
                                int min_key = -1;
                                int min_key_i;
                                int time = 0;
                                if (arr[0] &lt; arr[1])
                                {
                                    /*升序*/
                                    while (left &lt;= right)
                                    {
                                        time++;
                                         mid = left + (key - arr[left]) / (arr[right] - arr[left]) * (right - left);
                                        //说明key在arr[mid]和left之间
                                        if (arr[mid] > key)
                                        {
                                            right = mid - 1;
                                        }
                                        //说明key在arr[mid]和right之间
                                        else if (arr[mid] &lt; key)
                                        {
                                            left = mid + 1;
                                        }
                                        else
                                        {
                                            printf("Interpolation_search:         array[%d]:%d     time:%d\n", mid, key, time);
                                            break;
                                        }
                                    }
                                }
                                if (left > right)
                                {
                                    time++;
                                    for (int i = 0; i &lt; sz; i++)
                                    {
                                        if (arr[i] &lt; key)
                                        {
                                            min_key = arr[i];
                                            min_key_i = i;
                                        }
                                    }
                                    printf("Interpolation_search:         array[%d]:%d     time:%d\n", min_key_i, min_key, time);
                                }
                            
                                /*降序*/
                                left = 0;
                                right = sz - 1; //右边
                                if (arr[0] > arr[1])
                                {
                                    while (left &lt;= right)
                                    {
                                        time++;
                                         mid = left + (key - arr[left]) / (arr[right] - arr[left]) * (right - left);
                                        //说明key在arr[mid]和right之间
                                        if (arr[mid] > key)
                                        {
                                            left = mid + 1;
                                        }
                                        //说明key在arr[mid]和left之间
                                        else if (arr[mid] &lt; key)
                                        {
                                            right = mid - 1;
                                        }
                                        else
                                        {
                                            printf("Interpolation_search:         array[%d]:%d     time:%d\n", mid, key, time);
                                            break;
                                        }
                                    }
                                }
                                if (left > right)
                                {
                                    time++;
                                    for (int i = 0; i &lt; sz; i++)
                                    {
                                        if (arr[i] &lt; key && min_key == -1)
                                        {
                                            min_key = arr[i];
                                            min_key_i = i;
                                        }
                                    }
                                    printf("Interpolation_search5:         array[%d]:%d     time:%d\n", min_key_i, min_key, time);
                                }
                            }
                            
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            def interpolation_search(array, target):
                                low = 0
                                high = len(array) - 1
 
                                while low &lt;= high and array[low] &lt;= target &lt;= array[high]:
                                    # 使用插值公式计算估计位置
                                    pos = low + ((target - array[low]) * (high - low)) // (array[high] - array[low])
 
                                    if array[pos] == target:
                                        return pos  # 找到目标值，返回位置
                                    elif array[pos] &lt; target:
                                        low = pos + 1  # 在右半部分查找
                                    else:
                                        high = pos - 1  # 在左半部分查找
 
                                return -1  # 目标值不存在
 
 
                            # 示例用法
                            array = [1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
                            target = 12
 
                            result = interpolation_search(array, target)
 
                            if result != -1:
                                print(f"目标值 {target} 在数组中的位置是：{result}")
                            else:
                                print(f"目标值 {target} 未在数组中找到。")
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        import java.io.BufferedReader;
                        import java.io.IOException;
                        import java.io.InputStreamReader;
 
                        /**
                        * @author admin $
                        * @title $mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)
                        *
                        * 其中，key是要查找的键值，data[high]、data[low]是剩余待查找记录中的最大值和最小值。假设数据项数为n
                        * @description $
                        * @updateTime $ 20:11$ $
                        * @throws $
                        */
                        public class InterSearch {
                            public static void main(String[] args) throws IOException {
                                int val=1,num;
                                int data[]=new int[50];
                                String StrM;
                                BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
                                for (int i=0;i&lt;50;i++){
                                    data[i]=val;
                                    val+=((int )(Math.random()*100)%5+1);
                                }
                                while (true){
                                    num=0;
                                    System.out.println("输入查找的键值，输入-1结束");
                                    StrM=keyin.readLine();
                                    val=Integer.parseInt(StrM);
                                    if (val==-1)break;
                                    num=interpolation(data,val);
                                    if (num ==-1) {
                                        System.out.println("没有找到");
                                    }
                                    else System.out.println("在第"+(num+1)+"个位置找到["+data[num]+"]");
                                }
 
 
                            }
                            public static int interpolation(int data[],int val){
                                int low,mid,high;
                                low=0;
                                high=49;
                                int tmp;
                                while (low &lt;= high && val != -1) {
 
                                    tmp=(int)((float)(val-data[low])*(high-low)/(data[high]-data[low]));
                                    mid=low+tmp;
                                    if (mid>50||mid&lt;-1) return -1;
                                    if (val&lt;data[low]&&val&lt;data[high]) return -1;
                                    else if(val>data[low]&&val>data[high]) return -1;
                                    if (val==data[mid]) return mid;
                                    else if(val&lt;data[mid]){
                                        high=mid-1;
                                    }
                                    else  if(val>data[mid]){
                                        low=mid+1;
                                    }
                                }
                                return -1;
                            }
                        }
                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
